package com.mdnote.practice.dp;

import java.util.Arrays;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/21
 * @description 打家劫舍 II
 */
public class LeetCaode213 {


    public static void main(String[] args) {
        LeetCaode213 leetCaode213 = new LeetCaode213();
        int res = leetCaode213.rob(new int[]{1,2,3,1});
        System.out.println(res);
    }

    /**
     * 1. 重复子问题：
     * 2. 缓存中间结果
     * 3. DP方程： dp[i][0] = dp[i - 1][1] + num[i]
     *            dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1])
     *
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        if (nums.length == 0)
            return 0;
        if (nums.length == 1)
            return nums[0];

        //  第一个是第一个房间不偷的情况，第二种是不偷最后一个不偷
        return Math.max(rob_i(Arrays.copyOfRange(nums, 1, nums.length)),
                rob_i(Arrays.copyOfRange(nums, 0, nums.length - 1)));
    }

    public int rob_i(int[] nums) {
        int dp_get = nums[0];
        int dp_unGet = 0;
        for (int i = 1; i < nums.length; i++) {
            int temp_get = dp_get;
            int temp_unGet = dp_unGet;

            dp_get = temp_unGet + nums[i];
            dp_unGet = Math.max(temp_get, temp_unGet);
        }

        return Math.max(dp_get, dp_unGet);
    }
}
